/**
 * Trie (字典树/前缀树) 实现
 * 
 * Trie是一种树形数据结构，用于高效地存储和搜索字符串数据集中的键。
 * 这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
 * 
 * 时间复杂度：
 * - 插入: O(m) m为字符串长度
 * - 搜索: O(m) m为字符串长度
 * - 前缀搜索: O(m) m为字符串长度
 * 
 * 空间复杂度: O(ALPHABET_SIZE * N * M) N为字符串数量，M为平均字符串长度
 */

class TrieNode {
  constructor() {
    // TODO: 初始化子节点映射和结束标志
    // this.children = {}
    // this.isEndOfWord = false
  }
}

class Trie {
  constructor() {
    // TODO: 初始化根节点
    // this.root = new TrieNode()
  }

  /**
   * 向Trie中插入一个单词
   * @param {string} word - 要插入的单词
   */
  insert(word) {
    // TODO: 实现单词插入逻辑
    // 1. 从根节点开始
    // 2. 遍历单词的每个字符
    // 3. 如果字符不存在，创建新的TrieNode
    // 4. 移动到下一个节点
    // 5. 标记最后一个节点为单词结束
  }

  /**
   * 搜索Trie中是否存在指定单词
   * @param {string} word - 要搜索的单词
   * @returns {boolean} - 是否存在该单词
   */
  search(word) {
    // TODO: 实现单词搜索逻辑
    // 1. 从根节点开始
    // 2. 遍历单词的每个字符
    // 3. 如果字符不存在，返回false
    // 4. 移动到下一个节点
    // 5. 检查最后一个节点是否标记为单词结束
  }

  /**
   * 检查Trie中是否有以指定前缀开头的单词
   * @param {string} prefix - 要检查的前缀
   * @returns {boolean} - 是否存在以该前缀开头的单词
   */
  startsWith(prefix) {
    // TODO: 实现前缀搜索逻辑
    // 1. 从根节点开始
    // 2. 遍历前缀的每个字符
    // 3. 如果字符不存在，返回false
    // 4. 移动到下一个节点
    // 5. 如果所有字符都存在，返回true
  }

  /**
   * 从Trie中删除一个单词
   * @param {string} word - 要删除的单词
   */
  delete(word) {
    // TODO: 实现单词删除逻辑
    // 1. 使用递归辅助函数
    // 2. 如果到达单词末尾，取消结束标记
    // 3. 如果节点没有子节点且不是单词结束，删除该节点
    // 4. 返回是否应该删除当前节点
  }

  /**
   * 获取Trie中所有单词
   * @returns {string[]} - 所有单词的数组
   */
  getAllWords() {
    // TODO: 实现获取所有单词的逻辑
    // 1. 使用深度优先搜索遍历整个Trie
    // 2. 收集所有标记为单词结束的路径
    // 3. 返回单词数组
  }

  /**
   * 获取以指定前缀开头的所有单词
   * @param {string} prefix - 前缀
   * @returns {string[]} - 以该前缀开头的所有单词
   */
  getWordsWithPrefix(prefix) {
    // TODO: 实现获取指定前缀单词的逻辑
    // 1. 先找到前缀对应的节点
    // 2. 从该节点开始进行深度优先搜索
    // 3. 收集所有单词结束的路径
    // 4. 返回单词数组
  }
}

module.exports = Trie